#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;
/*
int up[20],down[20];
int a,n,m,x;
bool judge2(int target){
	up[2]=target;
	down[2]=target;
	for(int i=3;i<n;i++){
		up[i]=up[i-1]+up[i-2];
		down[i]=up[i-1];
	}
	
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=sum+up[i]-down[i];
	}
	
	if(sum==0)
	return true;
	else
	return false;
}
*/
/*
bool three(int x){
	int num[10];//0~9每个数字出现的次数num[x]=k，表示数字x出现了k次 
	int a[10];
	memset(num,0,sizeof(num));
	//存放x,2x,3x的每位数字的个十百位的数字 
	a[1]=x/100;
	a[2]=x%10;
	a[3]=(x/10)%10;
	
	//
	a[4]=(2*x)/100;
	a[5]=(2*x)%10;
	a[6]=((2*x)/10)%10;
	
	//
	a[7]=(3*x)/100;
	a[8]=(3*x)%10;
	a[9]=((3*x)/10)%10;

	for(int i=1;i<10;i++){
		num[a[i]]++;
	}
	
	for(int i=1;i<10;i++){//如果每位数字出现仅出现一次，满足条件，否则不满足条件 
		if(num[i]!=1)
		return false;
	}	
	return true;
}
*/
/*
int a1,a2,a3,a4,a5,a6;
bool canWeigh(int x){
	for(int num20=0;num20<=a6;num20++)
	for(int num10=0;num10<=a5;num10++)
	for(int num5=0;num5<=a4;num5++)
	for(int num3=0;num3<=a3;num3++)
	for(int num2=0;num2<=a2;num2++)
	for(int num1=0;num1<=a1;num1++)
	if(x==num20*20+num10*10+num5*5+num3*3+num2*2+num1)
	return true;
	
	return false;
}
*/

/*
typedef struct MaxIndex{
	int a,b;
	double value;
};
int lcd(int a,int b){
	if(a%b==0)
	return b;
	else
	return lcd(b,a%b);
}
double toDouble(int a,int b){
	return a*1.00/(b*1.0);
}
*/
/*
bool isPrime(int x){
	if(x<=1)
	return false;
	
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0)
		return false;
	}
	
	return true;
}
*/
/*
bool different(int a,int b,int c,int d,int e){
	if(a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&d!=e)
	return true;
	else
	return false;
}
*/
/*
typedef struct Garbage{
	int num;
	int x,y;
};
*/
/*
int w[5];
int R(int x){
	if(x==1)
	return (w[2]>w[1])+(w[3]==w[1]);
	else if(x==2)
	return (w[1]>w[2])+(w[1]>w[3]);
	else if(x==3)
	return (w[3]>w[2])+(w[2]>w[1]);
}
bool check(){
	if(w[1]==w[2]||w[1]==w[3]||w[3]==w[2])
	return false;
	if(R(1)==R(2)||R(1)==R(3)||R(3)==R(2))
	return false;
	if((w[1]>w[2])==(R(1)<R(2)))
	if((w[2]>w[3])==(R(2)<R(3)))
	if((w[1]>w[3])==(R(1)<R(3)))
	return true;
	
	return false;
}
*/
/*
typedef struct Person{
	char name;
	int weight;
};
int add(int a,int b){
	return a+b;
}
bool meetWeight(int zhao,int qian,int sun,int li){
	if(add(zhao,qian)==add(sun,li)&&add(zhao,li)>add(sun,qian)&&add(zhao,sun)<qian)
	return true;
	else
	return false;
	
}
struct Rule1{
	bool operator()(const Person &a1, const Person &a2){
		return a1.weight<a2.weight;
	}
};

*/
/*
int lcd(int a,int b){
	if(a%b==0)
	return b;
	else
	return lcd(b,a%b);
}
*/
/*
typedef struct Reader{
	int favoriteBook;
};
typedef struct Book{
	int readList[205];
	int readLen;
};
*/

/*
char result[6];
bool judgeOf(char ch){
	if(ch=='A')
	return result[1]=='E';
	
	if(ch=='B')
	return result[2]=='B';
	
	if(ch=='C')
	return result[5]=='A';
	
	if(ch=='D')
	return result[1]!='C';
	
	if(ch=='E')
	return result[1]=='D';
}
bool check(){
	if(result[2]!='E'&&result[3]!='E'&&judgeOf(result[1])&&judgeOf(result[2])&&judgeOf(result[3])==false&&judgeOf(result[4])==false&&judgeOf(result[5])==false)
	return true;
	else
	return false;
}
void output(char x){
	for(int i=1;i<=5;i++){
		if(result[i]==x)
		cout<<i<<endl;
	}
}
*/

/*
int numKTo10(int x,int k){
	int sum=0;
	int K=1;
	while(x!=0){
		int temp=x%10;
		if(temp>=k)
		return -1;
		else{
			sum+=temp*K;
			x/=10;
			K=K*k;
		}
		
	}
	return sum;
}
*/


/*
bool meetRequest(int a,int b,int c){
	if(a*a+b*b==c*c)
	return true;
	else
	return false;
}
*/
/*
int powOf2(int k){
	int res=1;
	while(k--)
	res*=2;
	
	return res;
}
int check(int ans[18][18],int N){
	int sum=0;
	for(int i=2;i<=N+1;i++){
		for(int j=1;j<=N;j++){
			int res=ans[i-1][j]|ans[i-1][j-1]|ans[i-1][j+1]|ans[i-2][j];
			if(res==0){
				ans[i][j]=1;
				sum++;
			}else
			ans[i][j]=0;
		}
	}
	return sum;
}
*/
/*
int block[7][8],ans[7][8];
bool check(){
	for(int i=2;i<=6;i++)
	for(int j=1;j<=6;j++){
		ans[i][j]=block[i-1][j]^ans[i-1][j]^ans[i-1][j-1]^ans[i-1][j+1]^ans[i-2][j];
	}
	
	for(int i=1;i<=6;i++){
		if(ans[6][i]==1)
		return false;
	}
	return true;
}
void solve(){
	
	for(int i=0;i<64;i++){
		int temp=i;
		for(int j=1;j<=6;j++){
			ans[1][j]=temp%2;
			temp/=2;
		}
		if(check()){
			break;
		}
	}
	
	for(int i=1;i<=5;i++)
	for(int j=1;j<=6;j++){
		if(j==6)
		cout<<ans[i][j]<<endl;
		else
		cout<<ans[i][j]<<' ';
	}
	
	
}

*/
/*
bool isTriple(int a,int b,int c,int d){
	if(a*a*a==b*b*b+c*c*c+d*d*d){
		return true;
	}else{
		return false;
	}
}
*/

/*
bool meetRequest(int a1,int a2,int a3){	
	if((a1+a2)%2==0&&(a2+a3)%3==0)
	return true;
	else
	return false;
}
*/
int main(){
	
	//01
	/*
	int n;
	cin>>n;
	int i=3*n;
	while(i%5!=0) i--; 
	
	for(;i>=0;i=i-5){
		int a1,a2,a3;
		for(a1=0;a1<=n;a1++){
			for(a2=0;a2<=n;a2++){
				a3=i-a1-a2;
				if(a3>n){
					continue;
				}
				if(meetRequest(a1,a2,a3)){
					cout<<i;
					return 0;
				}
			}
		}
		
	}
	
	*/
	
	
	
	//02
	/*
	int footNum;
	cin>>footNum;
	
	int maxNum,minNum;
	if(footNum%2==0){
		maxNum=footNum/2;
		minNum=footNum/4+(footNum%4)/2;		
	}else{
		maxNum=0;
		minNum=0;
	}

	cout<<minNum<<' '<<maxNum;
	*/
	
	
	//03
	/*
	int input[20];
	int i;
	for(i=0;i<16;i++){
		cin>>input[i];
		if(input[i]==0)
		break;		
	}	
	sort(input,input+i);
	
	int count=0;
	for(int j=0;j<i;j++){
		int x=input[j];
		for(int u=j+1;u<i;u++){
			if(input[u]==2*x){
				count++;
				break;			
			}
		}
	}
	
	cout<<count;
	
	*/
	
	
	//04
	/*
	int N;
	cin>>N;
	
	int a,b,c,d;
	for(a=4;a<=N;a++){
		for(b=2;b<=N;b++){
			for(c=b;c<=N;c++){
				for(d=c;d<=N;d++){
					if(isTriple(a,b,c,d))
					cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl;					
				}

			}
		}
	}
	*/
	
	
	//05
	/*
	for(int i=1;i<=5;i++){
		for(int j=1;j<=6;j++){
			int x;
			cin>>x;
			
			block[i][j]=x;
		}
	}
	solve();
	*/
	
	//画家问题 
	/*
	int N;
	cin>>N;
	
	int ans[18][18];
	int min=33333;
	for(int i=0;i<powOf2(N);i++){
		int temp=i;
		for(int j=1;j<=N;j++){
			ans[1][j]=temp%2;
			temp/=2;
		}
		
		int num=check(ans,N);
		if(num<min){
			min=num;
		}
		
	}
	
	cout<<min;
	
	*/
	
	
	//1943
	/*
	int a,b,c;
	
	for(int a=2;a<=100;a++)
	for(int b=a;b<=100;b++)
	for(int c=2;c<=100;c++){
		if(meetRequest(a,b,c))
		cout<<a<<"*"<<a<<" + "<<b<<"*"<<b<<" = "<<c<<"*"<<c<<endl;
	}
	
	*/
	
	//1973：确定进制 
	/*
	int p,q,r;
	cin>>p>>q>>r;
	
	for(int i=2;i<=16;i++){
		int pp=numKTo10(p,i);
		int qq=numKTo10(q,i);
		int rr=numKTo10(r,i);
		if(pp!=-1&&qq!=-1&&rr!=-1&&pp*qq==rr){
			cout<<i;
			return 0;
		}
	}
	
	cout<<"0";
	*/
	
	//1978:生理周期
	/*

	int p,e,i,d;
	cin>>p>>e>>i>>d;	

	int day;
	for(day=d+1;day<=21252;day++){
		if((day-p)%23==0)
		break;
	}
	
	for(;day<=21252;day+=23){
		if((day-e)%28==0)
		break;
	}
	
	for(;day<=21252;day+=23*28){
		if((day-i)%33==0)
		break;
	}
	
	cout<<day-d;
	*/
	
	
	//2472 子串计算  没算出来 
	/*
	char str[105];
	gets(str);
	char substr[10005][105];
	int top=-1;
	for(int i=0;i<strlen(str);i++) {
		for(int j=i+1;j<=strlen(str);j++){
			strcpy(str)
		}
	}
	*/
	
	
	//2673：比赛排名
	/*
	for(int a1=0;a1<5;a1++)
	for(int a2=0;a2<5;a2++)
	for(int a3=0;a3<5;a3++)
	for(int a4=0;a4<5;a4++)
	for(int a5=0;a5<5;a5++){
		if(a1!=a2&&a1!=a3&&a1!=a4&&a1!=a5&&a2!=a3&&a2!=a4&&a2!=a5&&a3!=a4&&a3!=a5&&a4!=a5){
			result[1]='A'+a1;
			result[2]='A'+a2;
			result[3]='A'+a3;
			result[4]='A'+a4;
			result[5]='A'+a5;
			
			if(check()){
				for(int i=0;i<5;i++)
				output('A'+i);
				return 0;	
			}
			
		}
		
	}
	*/
	
	//2722 和数
	/* 
	int n;
	cin>>n;
	int input[n];
	for(int i=0;i<n;i++){
		cin>>input[i];
	}
	
	sort(input,input+n);
	
	int num=0;
	for(int a=n-1;a>0;a--){
		for(int i=0;i<a-1;i++){
			if(binary_search(input+i+1,input+a,input[a]-input[i])){
				num++;
				break;
			}			
		}
	}

	cout<<num;
	*/
	
	//2723因子问题
	/*
	int N,M;
	cin>>N>>M;
	
	for(int a=1;a<=N;a++){
		if(N%a==0&&N%(M-a)==0){
			cout<<a;
			return 0;
		}
		
	} 
	cout<<"-1";
	*/
	
	//2983 谁是你潜在的朋友 
	/*
	int N,M;
	cin>>N>>M;
	
	Reader reader[N+5];
	Book book[M+5];
	for(int i=1;i<=M;i++){
		book[i].readLen=0;
	}
	for(int i=1;i<=N;i++){
		int x;
		cin>>x;
		reader[i].favoriteBook=x;
		book[x].readList[book[x].readLen]=i;
		book[x].readLen++;
	}
	
	for(int i=1;i<=N;i++){
		int len=book[reader[i].favoriteBook].readLen;
		if(len>1)
		cout<<len-1<<endl;
		else
		cout<<"BeiJu"<<endl;
	}
	*/
	
	
	//3526:最简真分数
	/*
	int n;
	cin>>n;
	int a[n+5];
	for(int i=1;i<=n;i++)
	cin>>a[i];
	
	
	int num=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(lcd(a[i],a[j])==1)
			num++;
		}
	}
	
	cout<<num;
	
	*/
	
	
	//6184 找和为K的两个元素
	/*
	int n,k;
	cin>>n>>k;
	
	int a[n+5];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	sort(a,a+n);
	
	for(int i=0;i<n-1;i++){
		if(binary_search(a+i+1,a+n,k-a[i])){
			cout<<"yes";
			return 0;
		}
	}
	
	cout<<"no";
	*/
	
	//6187:称体重
	/*
	int zhao,qian,sun,li;
	Person person[5];
	
	for(zhao=10;zhao<=50;zhao+=10)
	for(qian=10;qian<=50;qian+=10)
	for(sun=10;sun<=50;sun+=10)
	for(li=10;li<=50;li+=10){
		if(meetWeight(zhao,qian,sun,li)){
			person[0].name='z';
			person[0].weight=zhao;
			person[1].name='q';
			person[1].weight=qian;
			person[2].name='s';
			person[2].weight=sun;
			person[3].name='l';
			person[3].weight=li;
			
			sort(person,person+4,Rule1());
			for(int i=0;i<4;i++){
				cout<<person[i].name<<' '<<person[i].weight<<endl;
			}			
		}

	}
	*/
	
	//6188:比饭量
	/*
	for(int a=1;a<=3;a++)
	for(int b=1;b<=3;b++)
	for(int c=1;c<=3;c++){
		w[1]=a;
		w[2]=b;
		w[3]=c;
		
		if(check()){
			char res[4];
			res[a]='A';
			res[b]='B';
			res[c]='C';
			
			for(int i=1;i<=3;i++){
				cout<<res[i];
			}
			return 0;	
		}

	}
	
	cout<<"Hello wordl";
	*/
	
	
	//7213垃圾炸弹
	/*
	int d;
	int n;
	
	cin>>d>>n;
	Garbage g[n+5];  
	for(int i=0;i<n;i++){
		cin>>g[i].x>>g[i].y>>g[i].num;
	}
	
	int max=-1;
	int sameMax=0;
	for(int x=0;x<=1024;x++)
	for(int y=0;y<=1024;y++){
		int sum=0;
		for(int i=0;i<n;i++)
		if(abs(x-g[i].x)<=d&&abs(y-g[i].y)<=d){
			sum+=g[i].num;
			
		}
		
		if(sum>max){
			max=sum;
			sameMax=1;
		}else if(sum==max){
			sameMax++;
		}
	}
	
	cout<<sameMax<<' '<<max;
	*/
	
	
	//7216:Minecraft
	/*
	int n;
	cin>>n;
	
	if(sqrt(n)*sqrt(n)==n){
		
	}
	*/
	
	
	//7217:猴子吃桃
	/*
	int n,ans;
	cin>>n;
	for(int i=1;true;i++){
		ans=i*n+1;
		int j;
		for(j=1;j<n;j++){
			if(ans%(n-1)==0){
				ans=ans/(n-1)*n+1;
			}else
			break;
		}
		if(j==n){
			break;
		}
	}
	
	cout<<ans;
	*/
	
	//7621硬币面值组合
	/*		
	int n;
	scanf("%d",&n);
	
	int a,b,c;
	int NO=1; 
	for(c=0;c<=n/5;c++)
	for(b=0;b<=n/2;b++)
	for(a=0;a<=n/1;a++){
		if(a*1+b*2+c*5==n){
			if(NO<10)
			printf("00%d%12d%12d%12d\n",NO,a,b,c);
			else if(NO>=10&&NO<100)
			printf("0%d%12d%12d%12d\n",NO,a,b,c);
			else if(NO<1000)
			printf("%3d%12d%12d%12d\n",NO,a,b,c);
			NO++;
		}
	}
	*/
	
	//7623:五户共井问题	
	/*
	int kLimit,n1,n2,n3,n4,n5;
	scanf("%d %d %d %d %d %d",&kLimit,&n1,&n2,&n3,&n4,&n5);	
	
	int a,b,c,d,e,k;//分别表示a,b,c,d,e和井的长度 
	for(k=1;k<=kLimit*100;k++)
	for(a=1;a<=k/n1;a++){
		b=k-a*n1;
		c=k-b*n2;
		d=k-c*n3;
		e=k-d*n4;
		
		if(e*n5+a==k&&different(a,b,c,d,e)){
			printf("%d %d %d %d %d %d",k,a,b,c,d,e);
			return 0;
		}
	}
		
	if(k>kLimit*100)
	printf("not found");
	*/
	
	//7647:余数相同问题	
	/*
	int a,b,c;
	cin>>a>>b>>c;
	int xLimit=max(a,b);
	xLimit=xLimit>c?xLimit:c;
	
	for(int x=2;x<=xLimit;x++){
		if(a%x==b%x&&b%x==c%x){
			cout<<x;
			return 0;
		}
	}
	*/
	//7649:我家的门牌号
	/*
	int n;
	cin>>n;	
	
	int mine;
	int total;
	int sum;
	for(total=1;total<=50000;total++)
	for(mine=1;mine<=total;mine++){
		sum=(1+total)*total/2;
		if(sum-mine*2==n){
			cout<<mine<<' '<<total;
			return 0;
		}			
	}
	*/
	
	
	//7650:不定方程求解
	/*
	int a,b,c;
	int x,y;
	cin>>a>>b>>c;
	int count=0;
	for(x=0;x<=c/a;x++)
	for(y=0;y<=c/b;y++){
		if(a*x+b*y==c)
		count++;
	}
	
	cout<<count;
	*/
	
	//7827:质数的和与积
	/*
	int S;
	cin>>S;
	
	int max=-1;
	for(int x=2;x<=S/2;x++){
		int y=S-x;
		
		if(isPrime(x)&&isPrime(y)){
			int squre=x*y;
			
			if(squre>max)
			max=squre;
		}
	}
	
	cout<<max;
	*/
	
	//7832:最接近的分数	
	/*
	int N,A,B;
	cin>>N>>A>>B;
	
	double Limit=toDouble(A,B);
	MaxIndex max;
	max.value=-1;
	for(int b=1;b<=N;b++){//分母 
		for(int a=1;a<b;a++){//分子 
			double res=toDouble(a,b);
			if(res<Limit&&lcd(a,b)==1){
				if(res>max.value){
					max.value=res;
					max.a=a;
					max.b=b;
				}
			}
		}
	}
	
	cout<<max.a<<' '<<max.b;
	*/
	
	//8755:砝码称重	
	/*
	cin>>a1>>a2>>a3>>a4>>a5>>a6;
	int totalWeight=a1+a2*2+a3*3+a4*5+a5*10+a6*20;
	int Total=0;
	for(int weight=1;weight<=totalWeight;weight++){
		if(canWeigh(weight))
		Total++;
	} 
	
	cout<<"Total="<<Total;
	*/
	
	//8757:三个三位数
	/*
	int count=0;
	for(int i=1;i<=333;i++){
		if(three(i)){
			cout<<i<<' '<<2*i<<' '<<3*i<<endl;
		}
	}
	*/
	//8759:火车上的人数
	/*
	cin>>a>>n>>m>>x;	
	up[1]=a;
	down[1]=0;
	up[n]=0;
	down[n]=m;

	
	int i;
	for(i=0;i<=10000;i++){
		if(judge2(i))
		break;
	}
	up[2]=i;
	down[2]=i;
	
	
	int sum=0;
	for(int i=1;i<=x;i++){
		sum=sum+up[i]-down[i];
	}
	
	cout<<sum;
	*/
	
	
	//8760:Cantor表
	
	
			
	return 0;
}
